/**
 * 地下城
 * https://leetcode.cn/problems/dungeon-game/
 */
class Solution {
    public int calculateMinimumHP(int[][] d) {
        int m = d.length,n = d[0].length;

        int[][] dp = new int[m + 1][n + 1];

        for(int i = 0;i <= m;i++) dp[i][n] = Integer.MAX_VALUE;
        for(int j = 0;j <= n;j++) dp[m][j] = Integer.MAX_VALUE;

        dp[m][n-1] = 1;dp[m-1][n] = 1;

        for(int i = m-1;i >=0;i--)
            for(int j = n-1;j >= 0;j--)
            {
                dp[i][j] = Math.min(dp[i][j+1],dp[i+1][j]) - d[i][j];

                dp[i][j] = Math.max(1,dp[i][j]);
            }

        return dp[0][0];
    }
}

/**
 * 按摩师
 * https://leetcode.cn/problems/the-masseuse-lcci/submissions/678313139/
 */
class Solution2 {
    public int massage(int[] nums) {
        int n = nums.length;

        int g[] = new int[n + 1];
        int f[] = new int[n + 1];

        for(int i = 1;i <= n;i++){
            f[i] = nums[i -1] + g[i - 1];
            g[i] = Math.max(f[i-1],g[i-1]);
        }

        return Math.max(f[n],g[n]);
    }
}

/**
 * 打家劫舍11
 *https://leetcode.cn/problems/house-robber-ii/
 */
class Solution3 {
    public int rob(int[] nums) {
        int n = nums.length;

        return Math.max(rob1(nums,2,n-2) + nums[0],rob1(nums,1,n - 1));
    }

    private int rob1(int nums[],int left,int right){

        if(left > right) return 0;

        int n = nums.length;
        int f[] = new int[n];
        int g[] = new int[n];

        for(int i = left;i <= right;i++){
            f[i] = nums[i] + g[i-1];
            g[i] = Math.max(f[i-1],g[i-1]);
        }

        return Math.max(f[right],g[right]);
    }
}